/* 
 * 周教授讲授计算机算法课程，班上一共有72个学生。每一周，周教授都安排这些学生见一次面。
 * 有些周，周教授将72名学生分为每组8人，另外一些周，周教授将72名学生分为每组9人。
 * 只要两个学生被分在同一组，就算见一次面。周教授分组的原则是，在整个授课过程中，任意两
 * 个学生必须见一次面，且仅见一次面。问，周教授的课程需要安排多少周？周教授需要如何将这
 * 些学生分组？
 * 
 * 周教授有125名学生，将其分为25组，每组5名学生，周教授的课一共上31周。每一周，周教授
 * 让这些学生见一次面。如果算法课程结束时，任意两个学生恰好见了一次面，问，周教授如何分
 * 组？
 */

#include <stdio.h>
#include <assert.h>
#include <time.h>

const int STUDENT_NUM     = 72;
const int INIT_GROUP_NUM  = 9;
const int INIT_GROUP_SIZE = 8;
const int GROUP_NUM       = 8;
const int GROUP_SIZE      = 9;   

// 见面情况
int meeted[STUDENT_NUM][STUDENT_NUM] = {0};
void init_meeted()
{
    for (int i = 0; i < STUDENT_NUM; i++) {
        meeted[i][i] = 1;
    }
}
void print_meeted()
{
    printf("Meeted:\n");
    for (int i = 0; i < STUDENT_NUM; i++) {
        for (int k = 0; k < STUDENT_NUM; k++)
            printf("%2d", meeted[i][k]);
        printf("\n");
    }
}
bool solved()
{
    for (int i = 0; i < STUDENT_NUM; i++) {
        for (int k = 0; k < STUDENT_NUM; k++)
            if (!meeted[i][k]) return false;
    }
    return true;
}

/*  原始分组方案
    第1组：00 01 02 03 04 05 06 07
    第2组：08 09 10 11 12 13 14 15
    第3组：16 17 18 19 20 21 22 23
    第4组：24 25 26 27 28 29 30 31
    第5组：32 33 34 35 36 37 38 39
    第6组：40 41 42 43 44 45 46 47
    第7组：48 49 50 51 52 53 54 55
    第8组：56 57 58 59 60 61 62 63
    第9组：64 65 66 67 68 69 70 71
*/
int origin[INIT_GROUP_NUM][INIT_GROUP_SIZE] = {0};
void generate_origin()
{
    int num = 0;
    for (int i = 0; i < INIT_GROUP_NUM; i++)
        for (int k = 0; k < INIT_GROUP_SIZE; k++)
            origin[i][k] = num++;
}
void refresh_origin()
{
    for (int i = 0; i < INIT_GROUP_NUM; i++)
        for (int k = 0; k < INIT_GROUP_SIZE - 1; k++)
            for (int m = k + 1; m < INIT_GROUP_SIZE; m++) {
                meeted[origin[i][k]][origin[i][m]] = 1;
                meeted[origin[i][m]][origin[i][k]] = 1;
            }
}
void print_origin()
{
    printf("Origin:\n");
    for (int i = 0; i < INIT_GROUP_NUM; i++) {
        printf("Group[%d]:", i);
        for (int k = 0; k < INIT_GROUP_SIZE; k++)
            printf("%4d", origin[i][k]);
        printf("\n");
    }
}

// 解决方案
int solution[9][GROUP_NUM][GROUP_SIZE] = {0};
void generate_second_group()
{
    for (int i = 0; i < GROUP_NUM; i++)
        for (int k = 0; k < GROUP_SIZE; k++)
            solution[0][i][k] = origin[k][i];
}
void rotate(int week, int colm)
{
    int t = solution[week][GROUP_NUM - 1][colm];
    for (int i = GROUP_NUM - 1; i > 0; i--) {
        solution[week][i][colm] = solution[week][i - 1][colm];
    }
    solution[week][0][colm] = t;
}
void generate_new_group(int week)
{
    assert(week > 0);
    // 复制上一周的结果
    for (int i = 0; i < GROUP_NUM; i++)
        for (int k = 0; k < GROUP_SIZE; k++)
            solution[week][i][k] = solution[week-1][i][k];
    // 
    for (int i = 1; i < GROUP_NUM; i++)
        for (int k = 0; k < i; k++)
            rotate(week, i);
}
void refresh_meeted(int week)
{
    for (int i = 0; i < GROUP_NUM; i++)
        for (int k = 0; k < GROUP_SIZE - 1; k++)
            for (int m = k + 1; m < GROUP_SIZE; m++) {
                meeted[solution[week][i][k]][solution[week][i][m]] = 1;
                meeted[solution[week][i][m]][solution[week][i][k]] = 1;
            }
}
void print_group(int week, int id)
{
    printf("Group[%d]:", id);
    for (int i = 0; i < GROUP_SIZE; i++)
        printf("%4d", solution[week][id][i]);
    printf("\n");
}
void print_week(int week)
{
    printf("Week %d\n", week + 1);
    for (int i = 0; i < GROUP_NUM; i++)
        print_group(week, i);
}


int main()
{

    init_meeted();

    // 生成原始分组
    generate_origin();
    refresh_origin();
    print_origin();

    // 生成转置分组
    generate_second_group();
    refresh_meeted(0);
    print_week(0);

    for (int i = 1; i < 8; i++) {
        generate_new_group(i);
        refresh_meeted(i);
        print_week(i);
    }

    while(solved()) {
        // 找到第1个
    }

    print_meeted();
}